package com.kuang.linkedlist;

/*  给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。   */


/**
 * @author kjx
 */
public class ReverseList {


    //三指针尝试一波
    //这种思路是不断将某个节点丢到最前面，因此需要三个节点的信息，一个是头节点，其次是需要丢到最前面的节点，还有就是这个节点的前面一个节点
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //三指针,h始终保持为头节点,pq是不断向后的相邻指针
        ListNode h = head, p = head, q = head.next;
        while (q != null) {
            p.next = q.next;
            q.next = h;
            h = q;
            q = p.next;
        }
        return h;
    }


    //其实还有一种思路，双指针，一个是当前节点，一个是该节点前面一个节点
    //循环过程只需要不断将该节点指向前面那个节点就行，没必要说要指向头节点
    //但是这种思路不容易想，因此在循环的过程中，链表变化都是混乱不连续的，只有在最终结束的时候链表才是连通的
    //可以自己手动模拟一下，会发现一开始模拟会觉得很混乱，直到最后才豁然开朗
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curNode = head;    //cur是当前节点，一开始为head
        ListNode preNode = null;    //pre是当前节点前一个节点，头节点前面肯定是null啊
        while (curNode != null){
            ListNode nextNode = curNode.next;   //呃呃呃，其实还是要用到三个指针，只是思路不同
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }


}
